package com.xk._02算法篇._03graph;

import com.xk._02算法篇._03graph.graph.Graph;
import com.xk._02算法篇._03graph.graph.ListGraph;

import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * @description:
 * @author: xu
 * @date: 2022/10/5 20:09
 */
public class Main {
    static Graph.WeightManager<Double> weightManager = new Graph.WeightManager<Double>() {
        @Override
        public int compare(Double w1, Double w2) {
            return w1.compareTo(w2);
        }
        @Override
        public Double add(Double w1, Double w2) {
            return w1 + w2;
        }
        @Override
        public Double zero() {
            return 0.0;
        }
    };


    public static void main(String[] args) {
        //test01();
        //test02();
        //testBfs();
        //testDfs();
        //testTopo();
        //testMst();
        //testSp();
        testMultiSp();
    }

    static void testMultiSp(){
        Graph<Object, Double> graph = directedGraph(Data.NEGATIVE_WEIGHT1);
        Map<Object, Map<Object, Graph.PathInfo<Object, Double>>> paths = graph.shortestPaths();
        paths.forEach((Object from, Map<Object, Graph.PathInfo<Object, Double>> map) -> {
            System.out.println(from + ": ");
            map.forEach((Object to, Graph.PathInfo<Object, Double> path) -> {
                System.out.println("\t" + to + " -- " + path);
            });
        });
    }

    static void testSp(){
        Graph<Object, Double> graph = directedGraph(Data.SP);
        Map<Object, Graph.PathInfo<Object, Double>> sp = graph.shortestPath("A");
        if (sp != null) {
            sp.forEach((Object key, Graph.PathInfo<Object, Double> map) -> {
                System.out.println(key + " -- " + map);
            });
        }
    }

    static void testMst(){
        Graph<Object, Double> graph = undirectedGraph(Data.MST_02);
        Set<Graph.EdgeInfo<Object, Double>> edgeInfos = graph.mst();
        System.out.println("edgeInfos.size() = " + edgeInfos.size());
        edgeInfos.forEach(System.out::println);
    }

    private static void testTopo() {
        Graph<Object, Double> graph = directedGraph(Data.TOPO);
        List<Object> list = graph.topologicalSort();
        System.out.println(list);
    }

    static void testDfs() {
        Graph<Object, Double> graph = directedGraph(Data.DFS_02);
        graph.dfs("a", value -> {
            System.out.println(value);
            return false;
        });
    }

    static void testBfs() {
        Graph<Object, Double> graph = directedGraph(Data.BFS_02);
        graph.bfs(0, (value) -> {
            System.out.println(value);
            return false;
        });
    }

    // 无向图测试
    private static void test02() {
        /*Graph<String, Integer> graph = new ListGraph<>();

        graph.addEdge("V0", "V1");
        graph.addEdge("V1", "V0");

        graph.addEdge("V2", "V0");
        graph.addEdge("V0", "V2");

        graph.addEdge("V0", "V3");
        graph.addEdge("V3", "V0");

        graph.addEdge("V2", "V1");
        graph.addEdge("V1", "V2");

        graph.addEdge("V3", "V2");
        graph.addEdge("V2", "V3");

        graph.print();*/
    }
    // 有向图测试
    private static void test01() {
        /*Graph<String, Integer> graph = new ListGraph<>();
        graph.addEdge("V1", "V0", 9);
        graph.addEdge("V1", "V2", 3);
        graph.addEdge("V2", "V0", 2);
        graph.addEdge("V2", "V3", 5);
        graph.addEdge("V3", "V4", 1);
        graph.addEdge("V0", "V4", 6);

        *//*graph.print();
        System.out.println("*************************************************");*//*

        //graph.removeEdge("V0", "V4");
       *//* graph.removeVertex("V0");
        graph.print();

        System.out.println(graph.verticsSize());
        System.out.println(graph.edgesSize());*//*
        System.out.println("--------------------------------------");
        //graph.bfs("V1");*/
    }

    /**
     * 有向图
     */
    private static Graph<Object, Double> directedGraph(Object[][] data) {
        Graph<Object, Double> graph = new ListGraph<>(weightManager);
        for (Object[] edge : data) {
            if (edge.length == 1) {
                graph.addVertex(edge[0]);
            } else if (edge.length == 2) {
                graph.addEdge(edge[0], edge[1]);
            } else if (edge.length == 3) {
                double weight = Double.parseDouble(edge[2].toString());
                graph.addEdge(edge[0], edge[1], weight);
            }
        }
        return graph;
    }

    /**
     * 无向图
     * @param data
     * @return
     */
    private static Graph<Object, Double> undirectedGraph(Object[][] data) {
        Graph<Object, Double> graph = new ListGraph<>(weightManager);
        for (Object[] edge : data) {
            if (edge.length == 1) {
                graph.addVertex(edge[0]);
            } else if (edge.length == 2) {
                graph.addEdge(edge[0], edge[1]);
                graph.addEdge(edge[1], edge[0]);
            } else if (edge.length == 3) {
                double weight = Double.parseDouble(edge[2].toString());
                graph.addEdge(edge[0], edge[1], weight);
                graph.addEdge(edge[1], edge[0], weight);
            }
        }
        return graph;
    }
}
